package com.demo.java.OD251_300.OD257;

import java.util.*;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【硬件产品销售方案】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146054818
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取输入的目标金额
        int amount = Integer.parseInt(in.nextLine());
        // 读取输入的价格列表并处理格式
        String input = in.nextLine().replaceAll("\\s", "").substring(1).replaceAll("]", "");
        String[] arr = input.split(",");
        // 转换价格列表为整数数组
        int[] prices = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();
        // 对价格数组进行排序
        Arrays.sort(prices);

        // 用于存储组合的临时列表
        List<Integer> currentCombination = new ArrayList<>();
        // 用于存储所有符合条件的组合
        List<List<Integer>> result = new ArrayList<>();

        // 调用回溯函数进行递归
        findCombinations(prices, amount, currentCombination, result, 0);

        // 输出最终的结果
        System.out.println(result);
    }

    // 回溯函数
    public static void findCombinations(int[] prices, int amount, List<Integer> currentCombination, List<List<Integer>> result, int index) {
        // 如果金额为0，说明找到一个合法的组合
        if (amount == 0) {
            result.add(new ArrayList<>(currentCombination));
            return;
        }
        // 如果金额小于0，说明当前组合不合法
        if (amount < 0) return;

        // 从当前索引开始，尝试选择价格
        for (int i = index; i < prices.length; i++) {
            // 选择当前价格
            int price = prices[i];
            // 将当前价格加入组合
            currentCombination.add(price);
            // 递归调用，减少剩余金额
            findCombinations(prices, amount - price, currentCombination, result, i);
            // 回溯，移除当前价格
            currentCombination.remove(currentCombination.size() - 1);
        }
    }
}